package 力扣;

import Stack.Stack;

import javax.sound.midi.Soundbank;

/**
 * @author yyq
 * @create 2022-06-19 13:17
 */
public class leetcode1049 {
    public static void main(String[] args) {
        leetcode1049 leetcode1049=new leetcode1049();
        System.out.println(leetcode1049.lastStoneWeightII(new int[]{31, 26, 33, 21, 40}));
    }
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i = 0;i<stones.length;i++){
            sum = sum + stones[i];
        }
        int bag = sum/2 + 1;
        int[][] dp =new int[stones.length][bag];

        // dp数组初始化
        for (int i=0;i<dp.length;i++){
            dp[i][0] = 0;
        }
        for (int j=1;j<bag;j++){
            if(stones[0]<=j)
                dp[0][j] = stones[0];
            else dp[0][j] = 0;
        }

        // 完善dp数组
        for (int i=1;i<dp.length;i++){
            for(int j=1;j<bag;j++){
                if(j>=stones[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                }
                else dp[i][j] = dp[i-1][j];
            }
        }



        return Math.abs( sum-dp[dp.length-1][bag-1]*2);

    }
}
